home *** CD-ROM | disk | FTP | other *** search
/ MacFormat 1995 March / macformat-022.iso / Shareware City / Developers / src / out-of-phase-102-c / OutOfPhase 1.02 Source / OutOfPhase Folder / Level 0 Macintosh 29Sep94 / Array.c next >
Encoding:
C/C++ Source or Header  |  1994-11-23  |  8.0 KB  |  243 lines  |  [TEXT/KAHL]
  1. /* Array.c */
  2. /*****************************************************************************/
  3. /*                                                                           */
  4. /*    System Dependency Library for Building Portable Software               */
  5. /*    Macintosh Version                                                      */
  6. /*    Written by Thomas R. Lawrence, 1993 - 1994.                            */
  7. /*                                                                           */
  8. /*    This file is Public Domain; it may be used for any purpose whatsoever  */
  9. /*    without restriction.                                                   */
  10. /*                                                                           */
  11. /*    This package is distributed in the hope that it will be useful,        */
  12. /*    but WITHOUT ANY WARRANTY; without even the implied warranty of         */
  13. /*    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.                   */
  14. /*                                                                           */
  15. /*    Thomas R. Lawrence can be reached at tomlaw@world.std.com.             */
  16. /*                                                                           */
  17. /*****************************************************************************/
  18.  
  19. #include "MiscInfo.h"
  20. #include "Debug.h"
  21. #include "Audit.h"
  22. #include "Definitions.h"
  23.  
  24. #include "Array.h"
  25. #include "Memory.h"
  26.  
  27.  
  28. /* Abstract data structure for maintaining a linear array of elements.  It provides */
  29. /* indexed lookup, insertion, and deletion capabilities on the array, and attempts */
  30. /* to provide efficient storage management */
  31.  
  32.  
  33. /* when array runs out of free space at end, it is extended by ARRAYDELTACOUNT slots. */
  34. /* when there is more than ARRAYMAXFREECOUNT free space at the end, it is reduced */
  35. /* by ARRAYDELTACOUNT.  Therefore, ARRAYMAXFREECOUNT should be greater than */
  36. /* ARRAYDELTACOUNT to prevent resizing the array constantly. */
  37. #define ARRAYDELTACOUNT (32)
  38. #define ARRAYMAXFREECOUNT (64)
  39.  
  40. struct ArrayRec
  41.     {
  42.         long                    RealElementCount; /* actual number of elements in array */
  43.         long                    ListElementCount; /* number of slots in List */
  44.         void**                List;
  45.     };
  46.  
  47.  
  48. /* create a new array.  returns NIL if it couldn't allocate any memory. */
  49. ArrayRec*            NewArray(void)
  50.     {
  51.         return NewArrayReserveSpace(ARRAYDELTACOUNT);
  52.     }
  53.  
  54.  
  55. /* create a new array with preallocated space for a bunch of elements. */
  56. ArrayRec*            NewArrayReserveSpace(long NumElements)
  57.     {
  58.         ArrayRec*        Array;
  59.         void**            List;
  60.  
  61.         ERROR(NumElements < 0,PRERR(ForceAbort,"NewArrayReserveSpace:  bad reserve space"));
  62.         Array = (ArrayRec*)AllocPtrCanFail(sizeof(ArrayRec),"ArrayRec");
  63.         if (Array == NIL)
  64.             {
  65.              FailurePoint1:
  66.                 return NIL;
  67.             }
  68.         List = (void**)AllocPtrCanFail(sizeof(void*) * NumElements,"ArrayList");
  69.         if (List == NIL)
  70.             {
  71.              FailurePoint2:
  72.                 ReleasePtr((char*)Array);
  73.                 goto FailurePoint1;
  74.             }
  75.         Array->List = List;
  76.         Array->RealElementCount = 0;
  77.         Array->ListElementCount = NumElements;
  78.         return Array;
  79.     }
  80.  
  81.  
  82. /* dispose of an array.  any pointers contained in the array are NOT disposed. */
  83. void                    DisposeArray(ArrayRec* Array)
  84.     {
  85.         CheckPtrExistence(Array);
  86.         ReleasePtr((char*)Array->List);
  87.         ReleasePtr((char*)Array);
  88.     }
  89.  
  90.  
  91. /* get the number of elements currently stored in the array */
  92. long                    ArrayGetLength(ArrayRec* Array)
  93.     {
  94.         CheckPtrExistence(Array);
  95.         return Array->RealElementCount;
  96.     }
  97.  
  98.  
  99. /* get an indexed element from the array */
  100. void*                    ArrayGetElement(ArrayRec* Array, long Where)
  101.     {
  102.         CheckPtrExistence(Array);
  103.         ERROR((Where < 0) || (Where >= ArrayGetLength(Array)),
  104.             PRERR(ForceAbort,"ArrayGetElement:  Index out of range"));
  105.         return (Array->List)[Where];
  106.     }
  107.  
  108.  
  109. /* change the value of an indexed element in the array */
  110. void                    ArraySetElement(ArrayRec* Array, void* Element, long Where)
  111.     {
  112.         CheckPtrExistence(Array);
  113.         ERROR((Where < 0) || (Where >= ArrayGetLength(Array)),
  114.             PRERR(ForceAbort,"ArraySetElement:  Index out of range"));
  115.         (Array->List)[Where] = Element;
  116.     }
  117.  
  118.  
  119. /* insert an element into the array.  Where is the index of the element to insert */
  120. /* BEFORE.  if Where == number of elements in the array, the element is appended. */
  121. /* return True if successful */
  122. MyBoolean            ArrayInsertElement(ArrayRec* Array, void* Element, long Where)
  123.     {
  124.         CheckPtrExistence(Array);
  125.         ERROR((Where < 0) || (Where >/*NB*/ ArrayGetLength(Array)),
  126.             PRERR(ForceAbort,"ArrayInsertElement:  Index out of range"));
  127.         ERROR(Array->RealElementCount > Array->ListElementCount,
  128.             PRERR(ForceAbort,"ArrayInsertElement:  [pre] real count > list block count"));
  129.         if (Array->RealElementCount == Array->ListElementCount)
  130.             {
  131.                 long                NewSize;
  132.                 void**            NewList;
  133.  
  134.                 /* no free space at the end of the array, so we have to extend it */
  135.                 NewSize = Array->RealElementCount + ARRAYDELTACOUNT;
  136.                 NewList = (void**)ResizePtr((char*)(Array->List),NewSize * sizeof(void*));
  137.                 if (NewList == NIL)
  138.                     {
  139.                         return False;
  140.                     }
  141.                 Array->List = NewList;
  142.                 Array->ListElementCount = NewSize;
  143.             }
  144.         PRNGCHK(Array->List,&(Array->List[Where]),
  145.             (Array->RealElementCount - Where) * sizeof(void*));
  146.         PRNGCHK(Array->List,&(Array->List[Where + 1]),
  147.             (Array->RealElementCount - Where) * sizeof(void*));
  148.         MoveData((char*)&(Array->List[Where]),
  149.             (char*)&(Array->List[Where + 1]),
  150.             (Array->RealElementCount - Where) * sizeof(void*));
  151.         (Array->List)[Where] = Element;
  152.         Array->RealElementCount += 1;
  153.         ERROR(Array->RealElementCount > Array->ListElementCount,
  154.             PRERR(ForceAbort,"ArrayInsertElement:  [post] real count > list block count"));
  155.         return True;
  156.     }
  157.  
  158.  
  159. /* append an element to the end of the array.  returns True if successful */
  160. MyBoolean            ArrayAppendElement(ArrayRec* Array, void* Element)
  161.     {
  162.         CheckPtrExistence(Array);
  163.         return ArrayInsertElement(Array,Element,Array->RealElementCount);
  164.     }
  165.  
  166.  
  167. /* delete an element from the array and shift any elements after it down one. */
  168. void                    ArrayDeleteElement(ArrayRec* Array, long Where)
  169.     {
  170.         CheckPtrExistence(Array);
  171.         ERROR((Where < 0) || (Where >= ArrayGetLength(Array)),
  172.             PRERR(ForceAbort,"ArrayDeleteElement:  Index out of range"));
  173.         PRNGCHK(Array->List,&(Array->List[Where + 1]),
  174.             (Array->RealElementCount - Where - 1) * sizeof(void*));
  175.         PRNGCHK(Array->List,&(Array->List[Where]),
  176.             (Array->RealElementCount - Where - 1) * sizeof(void*));
  177.         MoveData((char*)&(Array->List[Where + 1]),(char*)&(Array->List[Where]),
  178.             (Array->RealElementCount - Where - 1) * sizeof(void*));
  179.         Array->RealElementCount -= 1;
  180.         if (Array->ListElementCount - Array->RealElementCount >= ARRAYMAXFREECOUNT)
  181.             {
  182.                 long                NewSize;
  183.                 void**            NewBlock;
  184.  
  185.                 /* if this fails, well... too bad */
  186.                 NewSize = Array->ListElementCount - ARRAYDELTACOUNT;
  187.                 ERROR(NewSize < 0,PRERR(ForceAbort,
  188.                     "ArrayDeleteElement:  reducing array to negative size"));
  189.                 NewBlock = (void**)ResizePtr((char*)(Array->List),NewSize * sizeof(void*));
  190.                 if (NewBlock != NIL)
  191.                     {
  192.                         Array->List = NewBlock;
  193.                         Array->ListElementCount = NewSize;
  194.                     }
  195.             }
  196.     }
  197.  
  198.  
  199. /* search the array to find the position of the specified element.  if the */
  200. /* element can't be found in the array, it returns -1. */
  201. long                    ArrayFindElement(ArrayRec* Array, void* Element)
  202.     {
  203.         long                    Scan;
  204.  
  205.         CheckPtrExistence(Array);
  206.         for (Scan = 0; Scan < Array->RealElementCount; Scan += 1)
  207.             {
  208.                 if ((Array->List)[Scan] == Element)
  209.                     {
  210.                         return Scan;
  211.                     }
  212.             }
  213.         return -1;
  214.     }
  215.  
  216.  
  217. /* return a duplicate of the array */
  218. ArrayRec*            DuplicateArray(ArrayRec* Original)
  219.     {
  220.         ArrayRec*        Copy;
  221.         long                ListSize;
  222.  
  223.         CheckPtrExistence(Original);
  224.         Copy = (ArrayRec*)AllocPtrCanFail(sizeof(ArrayRec),"ArrayRecDup");
  225.         if (Copy == NIL)
  226.             {
  227.              FailurePoint1:
  228.                 return NIL;
  229.             }
  230.         ListSize = PtrSize((char*)Original->List);
  231.         Copy->List = (void**)AllocPtrCanFail(ListSize,"ArrayListDup");
  232.         if (Copy->List == NIL)
  233.             {
  234.              FailurePoint2:
  235.                 ReleasePtr((char*)Copy);
  236.                 goto FailurePoint1;
  237.             }
  238.         CopyData((char*)Original->List,(char*)Copy->List,ListSize);
  239.         Copy->RealElementCount = Original->RealElementCount;
  240.         Copy->ListElementCount = Original->ListElementCount;
  241.         return Copy;
  242.     }
  243.